package jjn.round1;

/**
 * @author Jjn
 * @since 2022-08-15 18:38
 */
public class SortingAlgorithm_QuickSort implements SortAlgorithm {
    
    @Override
    public void sort(int... nums) {
        quickSort(0, nums.length - 1, nums);
    }
    
    private void quickSort(int l, int r, int... nums) {
        if (l >= r) {
            return;
        }
        int pivot = partition(l, r, nums);
        quickSort(l, pivot, nums);
        quickSort(pivot + 1, r, nums);
    }
    
    private int partition(int l, int r, int... nums) {
        int pivot = l + (int) (Math.random() * (r - l + 1));
        int pivotVal = nums[pivot];
        while (l <= r) {
            while (nums[l] < pivotVal) {
                l++;
            }
            while (nums[r] > pivotVal) {
                r--;
            }
            if (l == r) {
                break;
            }
            if (l < r) {
                int temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;
                l++;
                r--;
            }
        }
        return r;
    }
    
    @Override
    public String getName() {
        return "Quick sort";
    }
}
